package 数据结构和算法入门计划8月开始;

import java.util.Arrays;
// https://leetcode-cn.com/problems/boats-to-save-people/
public class 每日一题881救生艇0826 {
    // class Solution {
//     public int numRescueBoats(int[] people, int limit) {
//         int ans = 0;
//         // 从小到大排序，右边是最重的人
//         Arrays.sort(people);
//         int left = 0, right = people.length - 1;
//         while (left <= right) {
//             // 看右边的重量是否足够
//             if (people[right] == limit) {
//                 ans++;
//                 right--;
//             } else if (people[right] + people[left] <= limit) {
//                 // 再看最右边的人与最左边的人总体重量是否超过limit
//                 ans++;
//                 right--;
//                 left++;
//             } else {
//                 // 还是最右边的人单着
//                 ans++;
//                 right--;
//             }
//         }
//         return ans;
//     }
// }
    class Solution {
        public int numRescueBoats(int[] people, int limit) {
            int ans = 0;
            Arrays.sort(people);
            int light = 0, heavy = people.length - 1;
            while (light <= heavy) {
                if (people[light] + people[heavy] <= limit) {
                    ++light;
                }
                --heavy;
                ++ans;
            }
            return ans;
        }
    }


}
